package dp.公共子序列;

import java.util.Arrays;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 编辑距离72.java
 * @createTime 2024年03月01日 10:32:00
 */
public class 编辑距离72 {
	/*
    重复子问题
    状态：长度和操作
    定义函数dp(s1,i,s2,j)的返回值表示最小编辑操作
    如果si(i)=s2(j),则dp(s1,i,s2,j)=dp(s1,i-1,s2,j-1)
    如果si(i)≠s2(j)，那么有3中可能的选择,每次操作要+1表示一次选择
        1. 插入，dp(s1,i,s2,j-1)+1
        2. 替换，dp(s1,i-1,s2,j-1)+1
        3. 删除，dp(s1,i-1,s2,j)+1

     有重复子问题：dp[i][j]表示s1到i和s2到j的最小编辑操作为dp[i][j]
     取最小值
     baseCase;
     填充默认值-1
     边界：如果到了s1或者s2最开始，那么返回对方的长度

     */
	int[][] dp;

	public int minDistance(String word1, String word2) {
		int i = word1.length();
		int j = word2.length();
		dp = new int[i][j];
		for (int[] ints : dp) {
			Arrays.fill(ints, -1);
		}
		return dp(word1, i - 1, word2, j - 1);
	}

	public int dp(String s1, int i, String s2, int j) {
		if (i == -1) {
			return j + 1;
		}
		if (j == -1) {
			return i + 1;
		}
		//备忘录
		if (dp[i][j] != -1) {
			return dp[i][j];
		}
		if (s1.charAt(i) == s2.charAt(j)) {
			dp[i][j] = dp(s1, i - 1, s2, j - 1);
		} else {
			dp[i][j] =  Math.min(Math.min(dp(s1, i, s2, j - 1), dp(s1, i - 1, s2, j - 1)), dp(s1, i - 1, s2, j)) + 1;
		}
		return dp[i][j];
	}
}
